#!/usr/bin/env python3

class Node:
    def __init__(self, left=None, data=None, right=None):
        self.left = left
        self.data = data
        self.right = right
        self._size = None

    def size(self):
        if self._size is None:
            left_size = 0 if self.left is None else self.left.size()
            right_size = 0 if self.right is None else self.right.size()
            self._size = left_size + right_size + 1
        return self._size


def check_if_exist(node, parent_size=0):
    """
                parent_size
                     |
                   /   \
                l_size r_size
    """
    if node is None:
        return False
    left_size = 0 if node.left is None else node.left.size()
    right_size = 0 if node.right is None else node.right.size()

    parent_size_plus_self = parent_size + 1
    if parent_size_plus_self + left_size == right_size or parent_size_plus_self + right_size == left_size:
        return True
    elif parent_size_plus_self + left_size > right_size and parent_size_plus_self + right_size < left_size:
        return check_if_exist(node.left, parent_size_plus_self)
    elif parent_size_plus_self + right_size > left_size and parent_size_plus_self + left_size < right_size:
        return check_if_exist(node.right, parent_size_plus_self)
    else:
        return False
    
#            5
#           / \
#          1   6
#         /   / \
#        3   7   4
def _result_exist():
    node3 = Node(data=3)
    node1 = Node(left=node3, data=1)
    node7 = Node(data=7)
    node4 = Node(data=4)
    node6 = Node(left=node7, data=6, right=node4)
    node5 = Node(left=node1, data=5, right=node6)
    result = check_if_exist(node5)
    assert result

#           5
#          / \
#         1   6
#            / \
#           7   4
#          / \   \
#         3   2   8     
def _result_non_exist():
    node3 = Node(data=3)
    node2 = Node(data=2)
    node8 = Node(data=8)
    node4 = Node(data=4, right=node8)
    node7 = Node(left=node3, data=7, right=node2)
    node6 = Node(left=node7, data=6, right=node4)
    node1 = Node(data=1)
    node5 = Node(left=node1, data=5, right=node6)
    result = check_if_exist(node5)
    assert not result
    
if __name__ == '__main__':
    _result_exist()
    _result_non_exist()
    print("over")
